// Dijkstra's algorithm
/// # source-mat
const dijkstra = (
  edges: [string, string, number][],
  source: string,
  target: string,
) => {
  const Q = new Set<string>(),
    prev: Record<string, string> = {},
    dist: Record<string, number> = {},
    adj: Record<string, Record<string, number>> = {};

  for (let i = 0; i < edges.length; i++) {
    let v1 = edges[i][0],
      v2 = edges[i][1],
      len = edges[i][2];
    // wrapper method
    initQ.bind({ Q, dist, adj })(v1, v2, len);
    // Q.add(v1);
    // Q.add(v2);

    // dist[v1] = Infinity;
    // dist[v2] = Infinity;

    // if (adj[v1] === undefined) adj[v1] = {};
    // if (adj[v2] === undefined) adj[v2] = {};

    // adj[v1][v2] = len;
    // adj[v2][v1] = len;
  }
  /// start from `source`
  dist[source] = 0;
  // doFind
  while (Q.size) {
    let u = vertex_with_min_dist(Q, dist);
    if (u === null) continue;
    let neighbors = Object.keys(adj[u]).filter((v) => Q.has(v)); //Neighbor still in Q

    Q.delete(u);

    if (u === target) break; //Break when the target has been found

    for (let v of neighbors) {
      let alt = dist[u] + adj[u][v];
      if (alt < dist[v]) {
        dist[v] = alt;
        prev[v] = u;
      }
    }
  }

  let u = target,
    S = [u],
    len = 0;

  while (prev[u] !== undefined) {
    S.unshift(prev[u]);
    len += adj[u][prev[u]];
    u = prev[u];
  }
  return [S, len] as const;

  /**
   * 从给定的集合 Q 中找到距离最小的顶点
   * @param Q - 包含顶点的集合
   * @param dist - 记录每个顶点距离的对象
   * @returns 距离最小的顶点，如果 Q 为空则返回 null
   */
  function vertex_with_min_dist(
    Q: Set<string>,
    dist: Record<string, number>,
  ): string | null {
    let min_distance = Infinity,
      u = null;

    for (let v of Q) {
      if (dist[v] < min_distance) {
        min_distance = dist[v];
        u = v;
      }
    }
    return u;
  }
  // out-pack method
  function initQ(
    this: {
      Q: Set<string>;
      dist: Record<string, number>;
      adj: Record<string, Record<string, number>>;
    },
    v1: string,
    v2: string,
    len: number,
  ) {
    this.Q.add(v1);
    this.Q.add(v2);

    this.dist[v1] = Infinity;
    this.dist[v2] = Infinity;

    if (this.adj[v1] === undefined) this.adj[v1] = {};
    if (this.adj[v2] === undefined) this.adj[v2] = {};

    this.adj[v1][v2] = len;
    this.adj[v2][v1] = len;
  }
};

// export = { dijkstra };

//Testing algorithm
let graph: [string, string, number][] = [];
graph.push(['a', 'b', 7]);
graph.push(['a', 'c', 9]);
graph.push(['a', 'f', 14]);
graph.push(['b', 'c', 10]);
graph.push(['b', 'd', 15]);
graph.push(['c', 'd', 11]);
graph.push(['c', 'f', 2]);
graph.push(['d', 'e', 6]);
graph.push(['e', 'f', 9]);
// TODO: use D3
let [path, length] = dijkstra(graph, 'a', 'e');
console.log(path); //[ 'a', 'c', 'f', 'e' ]
console.log(length); //20

// const b = [1, 2, 3] as unknown as [number, number, string];
// //    ^?
// type e = EventTarget extends Event ? 1 : 0;
// //   ^?

